package _02_并查集;
/*
    QuickUnion->基于rank的优化 - 路径分裂
 */
public class QuickUnion_Rank_PS extends QuickUnion_Rank{
    public QuickUnion_Rank_PS(int capacity) {
        super(capacity);
    }

    /*
        使路径上的每个节点都指向祖父节点
     */
    @Override
    public int find(int v) {
        rangeCheck(v);

        while(v!=parents[v]){
            int p = parents[v];
            parents[v] = parents[parents[v]];
            v = p;
        }
        return v;
    }
}
